package com.year_23.may;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: jsh
 * @create: 2023/5/24 22:07
 * @Description:
 * @FileName: Day24
 * @History:
 * @自定义内容：
 */
public class Day24 {

    private double res;

    public double frogPosition(int n, int[][] edges, int t, int target) {
        List<Integer>[] g = new ArrayList[n+1];
        Arrays.fill(g, new ArrayList<>());
        g[1].add(0);
        for (int[] arr : edges) {
            int x = arr[0];
            int y = arr[1];
            g[x].add(y);
            g[y].add(x);
        }
        // 邻接表、目标数、当前位置、前一位置、所剩时间、在当前位置的概率
        dfs(g, target, 1, 0, t, 1);
        return res;
    }

    private boolean dfs(List<Integer>[] g, int target, int x, int fa, int t, int prod) {
        // t
        if (x == target && (t == 0 || g[x].size() == 1))  {
            res = 1.0 / prod;
            return true;
        }
        if (x == target || t == 0) return false;
        for (int y : g[x]) {
            if (y !=  fa && dfs(g, target, y, x, t-1, prod * (g[x].size() - 1)))
                return true;
        }
        return false;
    }
}
